package LinkList;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: LinkList
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-11-02  22:43
 * @Description: TODO
 * @Version: 1.0
 */
public class 重排链表143 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    ListNode midListnode(ListNode head){
        if (head==null){
            return head;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

    ListNode reverseListnode(ListNode head){
        ListNode pre=null;
        ListNode curr=head;
        while (curr!=null){
            ListNode future=curr.next;
            curr.next=pre;
            pre=curr;
            curr=future;
        }
        return pre;
    }
    public void mergenode(ListNode head1,ListNode head2){
        ListNode l1_tmp;
        ListNode l2_tmp;
        while (head1 != null && head2 != null) {
            l1_tmp = head1.next;
            l2_tmp = head2.next;

            head1.next = head2;
            head1 = l1_tmp;

            head2.next = head1;
            head2 = l2_tmp;
        }
    }

    public void reorderList(ListNode head) {
        if (head==null){
            return;
        }
        ListNode mid = midListnode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverseListnode(l2);
        mergenode(l1,l2);
    }
}
